Low basis theorem

The low basis theorem in computability theory states that every nonempty $\Pi^0_1$ class of $2^\omega$ (see analytical hierarchy) contains a set of low degree. It was first proved by Carl Jockusch and Robert I. Soare in 1972.

References

Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7
CG Jockusch, Jr and RI Soare, "Π(0, 1) Classes and Degrees of Theories" in Transactions of the American Mathematical Society (1972). JSTOR 1996261

‹The stub template below has been proposed for renaming to . See stub types for deletion to help reach a consensus on what to do.
Feel free to edit the template, but the template must not be blanked, and this notice must not be removed, until the discussion is closed. For more information, read the guide to deletion.›